1. Field of the Invention
The present invention relates the scheduling of performance requests in Video-On-Demand (VOD) systems.
2. Background of the Invention
In Video-on-Demand systems, popular videos (i.e. movies or other programs) are often requested by many viewers. In order to increase system throughput, some viewers requesting an identical video may be transmitted (and hence share) a single video stream. This is referred to in the art as "batching".
Depending upon the system load, a requested video may not be started immediately. While viewers will usually tolerate a small wait time, a long wait may result in the loss (or "defection") of viewers. This may be accomplished, for example, by the viewer indicating (either actively or passively) that he is no longer interested in viewing the requested video.
A conventional approach to video scheduling is the use of a first-come-first-serve (FCFS) policy. Under this policy, all video requests are placed in a single request queue. The request at the front of the queue is sewed when system capacity is available to service the request. If batching is supported, all subsequent queued requests for the same video as the serviced request are also serviced from the same signal stream.
An alternative to the above approach is to maintain a separate request queue for each video and to select the video with the longest queue for the next showing. This is referred to as the longest queue length first (LQF) policy. Still another approach is to provide periodic showing (say every 5 minutes) for the most popular videos. For requests which would not be serviced by periodic showings, another scheduling scheme such as FCFS can be used.
As mentioned above, a viewer with a waiting request may defect if the waiting time exceeds the viewer's tolerance. Viewer defection is, of course, undesirable. The choice of video scheduling policy can have a significant effect on the amount of batching and defection. The FCFS policy does not take into account the batch size. By contrast, the LQF policy ignores the wait time already incurred by the waiting requests. Periodic showing (when used alone) may not provide the flexibility needed to cope with dynamic load variations.
Recently, a new approach oil batching was proposed in Shachnai, H., and Yu, P., The Role of Wait Tolerance in Effective Batching: A Paradigm for Multimedia Scheduling Schemes, IBM Research Report RC 20038, Apr. 1995, which is incorporated herein by reference. Under this approach, the additional wait time that viewers will tolerate before defecting, in addition to a video's respective queue length, is considered in making scheduling decisions. When system capacities become available, rather than scheduling the video immediately, the scheduler delays transmission of the video until just prior to expiration of the maximum wait tolerance time of the longest waiting one of the pending transmission requests. In the interim, additional requests for transmission of the video may join the queue. In contrast with LQF, a video with the longest queue may not get scheduled if all waiting requests are fairly recent. This prevents the most popular videos from monopolizing the stream capacities. In contrast with FCFS, better batching is achieved. To effectively implement this algorithm, however, knowledge of viewer tolerance is required. This knowledge may not be readily available.